package 数据结构.章节09;

/**
 * @author 挚爱之夕
 * @date 2021/10/11 - 10 - 11 - 22:44
 * @Description: 数据结构.章节09
 * @Version: 1.0
 */
public class _153_倒数第k个节点 {
    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 3, 4, 5};
        //创建链表
        Node head = new Node(a[0]);
        Node p = head;
        for (int i = 1; i < a.length; i++) {
            p.next = new Node(a[i]);
            p = p.next;
        }
        //检验是否成功创建
        p = head;
        while (p != null) {
            System.out.println(p.value);
            p = p.next;
        }
        System.out.println("________________________");
        //倒数第k个
        Node ans = getKOfTail(head, 1);
        System.out.println(ans.value);
    }

    private static class Node {
        Object value;
        Node next;

        public Node(Object value) {
            this.value = value;
        }
    }

    //双行指针，p1、p2间隔k，p2走到null，p1为倒数第k个
    private static Node getKOfTail(Node head, int k) {
        if (head == null || k <= 0) {
            return null;
        }
        Node p1 = head, p2 = p1;
        int count = 0;
        while (p2 != null) {
            p2 = p2.next;
            count++;
            if (count == k)
                break;
        }
        //链表长度小于k
        if (count < k)
            return null;

        while (p2 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;

    }
}
